// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

// 看了题解，动态规划
// 不同的是，原来设想存当前该节点最长，现在存储包括当前节点的最长

// 执行用时：
// 280 ms
// , 在所有 C++ 提交中击败了
// 44.34%
// 的用户
// 内存消耗：
// 10.3 MB
// , 在所有 C++ 提交中击败了
// 37.39%
// 的用户

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==1){
            return 1;
        }
        vector<int> dp(nums.size(),1);
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};